Diffie-Hellman (DH) key agreement is a fundamental development in cryptography. It is the first workable method of public-key cryptography, that made key distribution feasible without setting up pre-arranged secrets.
In the simplest form of the DH key agreement, each party has a respective private key x, y from which a public key αx, αy respectively, can be derived. By exchanging public keys, each party can compute a shared secret key αxy by combining the private and public keys. The function used to derive a public key from a private key is a one way function that makes computation of the public key relatively simple but renders it infeasible to extract the private key from the public key. Such a function is based on the difficulty of factoring large numbers which are the product of two large primes or the discrete log problem over finite fields.
Diffie-Hellman (DH) key agreement is in wide use today. The IPSec protocol uses DH key agreement, and IPSec is used in most Virtual Private Networks (VPNs) that most corporations use for allowing employees to connect remotely to the corporate network, as well as for connecting separate offices over the open Internet.
Diffie-Hellman key agreement is also a NIST recommended option in the Transport Layer Security (TLS) protocol. The TLS protocol is the successor to the SSL protocol. These protocols are used widely today for securing sensitive web traffic, such as online banking.
Static DH key agreement is a variant of DH key agreement in which one of the private keys is static, which means that it is a long term key to be used multiple times.
Because of the sensitivity of the private key, particularly where it is used multiple times, it is usually located in a private key module, which is an implementation that includes the private key operation. Generally, such modules include measures to prevent extraction of the private key, and to a much more limited extent, abuse of the private key operation. For example, these modules can be implemented in specialized hardware that does not admit the loading of malicious software such as viruses, worms and Trojan horses. Generally, such anti-tampering measures are expensive to implement. Therefore, to reduce costs, modules are generally designed with a minimum functionality. That way, the least amount of functionality needs anti-tampering protection.
By way of a simple example, a module may be a smart card. The smart card is owned by a user. Suppose that the user wishes to make a secure connection to a destination, such as a home computer from some remote computer. The user enters the smart card into a smart card reader attached to the remote computer. Then a connection is made to the home computer. The home computer authenticates the user by sending a challenge. The remote computer forwards the challenge to the smart card. The smart card signs the challenge, which is then forwarded back to the home computer. The home computer verifies the challenge and then provides the necessary access to the user via the remote computer. This allows the user to move around to different remote computers. The remote computers, however, should not be able to extract the user's private key from the smart card. That is, they should only be able to connect to the home computer while the user leaves the smart card in the reader. (For this to be achieved, a more sophisticated method than simple challenge and response is needed. Instead, the smart card may need to perform regular authentication of traffic or even encryption and decryption of all of the traffic.)
To enhance security further, a key derivation function (KDF), which is a one-way function applied to the raw DH shared secret, is often specified. Some standards specify that a KDF is to be used with DH key agreement. Different standards recommend different KDFs, however. For example, ANSI specifies several different KDFs, as does IEEE, as do SSL and TLS, and different yet again is IPSec.
The following provides a simplified description of the details behind two standardized key derivation functions. These are the ANSI X9.63 key derivation and the TLS key derivation functions.
The ANSI X9.63 key derivation is computed as follows. The input has three components. The first input component is Z, which is a secret value shared between the private key module and the destination, for example, the home computer in the simple example above. This shared secret value Z is not to be revealed to any gateway, such as the remote computer in the example above. The second input component is an integer key datalen, which is the length in octets of the keying data to be generated. The optional third input component is an octet string SharedInfo, which consists of some data shared by the entities who share the shared secret value Z. Furthermore, SharedInfo can also optionally be given an encoding of the Abstract Syntax Notation One (ASN.1), which includes 5 fields: an algorithm identifier, optional identifiers for each of the two entities, optional public shared information and optional private shared information. Evaluation of the KDF on this input then proceeds as follows.
The first steps of the ANSI X9.63 key derivation function are certain consistency checks made on the lengths of the inputs and the desired output length keydatalen. Then a 4-octet integer counter j is initialised with value 1. A series of hash values Kj are computed as follows: Kj=SHA-1(Z∥j∥[SharedInfo]), where ∥ indicates concatenation and [ ] indicates that the bracketed input is optional. The number t of these outputs depends on keydatalen. The hash values are concatenated to form a octet string K′=K1∥K2∥ . . . ∥Kt. The octet string is truncated to a shorted octet string K by taking the leftmost keydatalen octets. The output of the ANSI X9.63 KDF is K.
In the TLS standard, key derivation functions are called pseudorandom functions (PRF). The construction of the TLS PRF is quite different from the ANSI X9.63 KDF, and is given as follows. The construction makes use of an auxiliary construction HMAC, which is described first.
The HMAC construction can be built on any hash function. When the HMAC construction is used with a hash function; such as MD5 and SHA-1, then the resulting function is labelled HMAC-Hash, where Hash is the name of the hash function. The TLS PRF uses HMAC-SHA-1 and HMAC-MD5. The generic form of HMAC, namely HMAC-Hash, operates as follows.
The inputs to HMAC are a secret key K and a message M. The output is a tag T. The HMAC tag is computed as T=Hash((C+K)∥Hash((D+K)∥M)) where ∥ indicates concatenation, + indicates the well-known bit-wise exclusive-or (XOR) operation, and C and D are constant bit strings as determined by the HMAC algorithm. More precisely, the key K is padded with zero bits until its length matches that of C and D, except if K is longer than C and D, in which case, K is replaced with the hash of the key. This is written as:T=HMAC-Hash(K,M).
The function HMAC-Hash is used in another auxiliary hash-generic construction in TLS PRF, called P_Hash. The construction for P_Hash is as follows:P_Hash(Z,seed)=HMAC-Hash(Z,A(1)∥seed)∥HMAC-Hash(Z,A(2)∥seed)∥HMAC-Hash(Z,A(3)∥seed)∥ . . .where ∥ indicates concatentation and A( ) is defined as follows:A(0)=seed; A(j)=HMAC_Hash(Z,A(j−1)).
P_Hash can be iterated as many times as necessary to produce the necessary amount of data As with the ANSI X9.63, the truncation of the final (rightmost) bytes is used when the resulting concatenation of HMAC tags is longer than the amount of data needed.
The TLS PRF is defined as follows:PRF(Z,label,seed)=P_MD5(S1,label∥seed)+P_SHA-1(S2,label∥seed)where, as usual, + indicates exclusive-or and ∥ indicates concatenation. The values S1 and S2 are obtained by partitioning the octet string secret Z into two halves, the left half being S1 and right half S2, with the left half being large secret has an odd number of octets.
Because the MD5 outputs as specified by the algorithm are 16 octets while the SHA-1 outputs are 20 octets, the function P_MD5 will generally use more iterations than P_SHA-1.
The TLS PRF is used extensively in the TLS protocol. For example, it is used to derive a master secret from a pre-master secret, and it is also used to derive an encryption key from the master key, and so on.
The disharmony between standards on KDF creates a large incentive to module implementers either to support DH key agreement without the KDF, or to support just a limited number of KDFs.
The standard Public Key Cryptography Standard (PKCS) #11: Cryptographic Token Interface (cryptoki) addresses an interface for tokens such as smart cards, which are a class of private key modules. In this standard, a few KDFs are supported, but the interface provided are generally not KDF-flexible. The standard FIPS 140-2 also specifies requirement for private key modules. It explicitly requires that the cryptographic values such as raw DH shared secret values do not depart the security boundary of the private key module, but it does not provide a precise mechanism for key derivation.
The inventors have discovered that improper re-use of a static DH private key can ultimately result in recovery of the private key by an adversary. More precisely, when a shared secret established via static DH key agreement is used without application of a key derivation function (KDF), an adversary can launch an attack where multiple different shared keys are established and used, thereby recovering the static DH private key.
The inventors' recent discovery means that the option of implementing DH without KDF can be a security risk. Supporting a reduced number of KDF's may be too limiting: for example, it may require hardware upgrade just to use a new application standard.
As standards do not agree on key derivation functions, the module for performing a DH private key operation must somehow support multiple different KDF standards. One approach is for the module to implement all the KDF algorithms, which can be expensive because the module must support multiple different KDFs and limiting because the module cannot support new KDFs when these arise. The opposite approach is for the module to provide unprotected access to the raw DH private key operation, and let the application using the module apply the KDF. However, this renders the private key vulnerable to the recently discovered attacks.
It is an object of the present invention to obviate or mitigate the above disadvantages.